/**
 * 84. 柱状图中最大的矩形
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */

/**
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {
  const stack = new Array(heights.length).fill(0);
  let top = -1;
  const lowersLeft = new Array(heights.length).fill(-1);
  const lowersRight = new Array(heights.length).fill(heights.length);
  for (let i = 0; i < heights.length; i += 1) {
    while (top >= 0 && heights[stack[top]] >= heights[i]) {
      top -= 1;
    }
    lowersLeft[i] = top >= 0 ? stack[top] : -1;
    top += 1;
    stack[top] = i;
  }
  top = -1;
  for (let i = heights.length - 1; i >= 0; i -= 1) {
    while (top >= 0 && heights[stack[top]] >= heights[i]) {
      top -= 1;
    }
    lowersRight[i] = top >= 0 ? stack[top] : heights.length;
    top += 1;
    stack[top] = i;
  }
  let max = 0;
  for (let i = 0; i < heights.length; i += 1) {
    const area = heights[i] * (lowersRight[i] - lowersLeft[i] - 1);
    if (area > max) {
      max = area;
    }
  }
  return max;
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]) === 10);
console.log(largestRectangleArea([2, 4]) === 4);
